Digital imaging technology continues to improve and find widespread acceptance in both consumer and industrial applications. Digital imaging sensors are now commonplace in video movie cameras, security cameras, video teleconference cameras, machine vision cameras and, more recently, hand-held bar code readers. As each application matures, the need for intelligent image processing techniques grows. To date, the large data volume attendant to transmitting a digital image from one location to another could only be accomplished if the two locations were connected by a wired means. Machine vision and imaging-based automatic identification applications required significant computing power to be effective and correspondingly require too much electricity to be useful in portable applications. The trend now in both consumer and industrial markets is toward the use of portable wireless imaging that incorporates automatic identification technology.
Historically, the automatic identification industry has relied on laser technology as the means for reading bar codes. Laser scanners generate a coherent light beam that is oriented by the operator to traverse the horizontal length of the bar code. The reflected intensity of the laser beam is used to extract the width information from the bars and spaces that are encountered. Laser scanners are effective in reading linear bar codes such as the U.P.C. code (found in retail point-of-sale applications), Code 39, Interleaved 2 of 5, or the like. Information stored in these linear (1D) bar codes is used to represent a short message or an index number related to a separate data file located in a central computer.
Imaging-based scanners use a solid-state image sensor such as a Charge Coupled Device (CCD) or a Complimentary Metal Oxide Semiconductor (CMOS) imager to convert an image scene into a collection of electronic signals. The image signals are processed so that any machine-readable character or bar code found in the field of view can be located in the electronic representation of the image and subsequently interpreted. The ability of image-based readers to capture an electronic image of a two-dimensional area for later processing makes them well suited for decoding all forms of machine-readable data at any orientation.
There are a number of advantages realized by using stacked-bar or matrix-type 2D bar codes. Due to the large capacity of 2D codes, an entire data record can be stored in the symbol. This means that instead of referencing a separate central computer data file upon reading the symbol, related information such as unit price, shipping destination, production history or any other user data can be extracted from the symbol itself. 2D bar codes are more compact and take up less label area than 1D codes while storing far more data.
All bar codes contain a number of common components that allow a reader to recognize and decode the symbol correctly. The code reader must be able to locate the code in a field of view, identify the type of bar code, determine the dimensions of the code, and then correctly decode the symbol in the presence of errors.
Linear bar codes and stacked linear bar codes possess a xe2x80x9cstart barxe2x80x9d pattern and a xe2x80x9cstop barxe2x80x9d pattern that serve to identify both the type of bar code and the boundaries of the information. Matrix-type bar codes possess a xe2x80x9cfinder patternxe2x80x9d that serves the same purpose. Matrix code finder patterns are found either on the perimeter of the code or can be part of the internal structure of the code. Finder patterns typically incorporate additional information that allows the reader to determine code orientation.
Some 2D matrix codes can take on a number of allowed sizes or information densities. These types of codes must include easily detectable information that allows the reader to determine the bar code element size: the minimum height and width of a black or white area or xe2x80x9ccellxe2x80x9d in the code. Matrix codes typically possess a physical symmetry between the external size and the size of an individual cell. It is possible to determine the number of rows and columns of the matrix by knowing only the length of one side and the size of a single cell. For example, if an object within an image is found to be 100,000 pixels in height and the minimum distance between dark to light transitions is 7,962 pixels, the matrix height in elements can be calculated by dividing 100,000 by 7,962=13 elements high. For codes where only one physical size and information density is allowed, the number of rows and columns are known quantities. Although 2D bar codes are more compact than 1D codes, special care must be taken to ensure that the data stored in the code can be properly extracted. 1D codes provide xe2x80x9cinformation redundancyxe2x80x9d in the vertical direction. The taller the 1D codes, the greater the likelihood that a scan line will find and traverse an undamaged portion of the code thereby allowing a successful decode. 2D codes have built-in error detection and xe2x80x9cerror correctionxe2x80x9d data to allow the decoder to successfully decode a symbol even if part of the code is damaged or missing.
There are currently a wide variety of 2D codes that are in general use. Each code has a unique way of combining the three basic elements described above. Three of the most commonly used 2D codes include Data Matrix, PDF417, and MaxiCode.
Data Matrix is a matrix-type of 2D bar code that comes in a number of different array sizes and is identifiable by a finder pattern that occupies the perimeter of the optical code. The bottom and left edges of the code are solid black bars, forming an L-shaped pattern. The top and right edges of the code are made up of alternating black and white cells, allowing the reader to determine the number of rows and columns present in the matrix. The Data Matrix standard (ref) defines different types and levels of error correction, the preferred of which is ECC200. ECC200 uses a Reed-Solomon error correction scheme to allow the user to detect and correct a number of damaged bytes. Although most Data Matrix codes have an equal number of rows and columns, the standard allows for rectangular codes where there are twice the number of columns as rows.
PDF417 is a stacked-bar type of 2D bar code. PDF417 codes can be produced at a number of different aspect ratios, but are typically rectangular in shape. The code is identified by a start pattern that occupies the entire left edge of the symbol and a stop pattern occupying the entire right edge of the symbol. Data is stored in rows, with each row encoding the information in one of three schemes. Adjacent rows use different schemes, so the reader can correctly determine which row is being scanned. The code is also divided horizontally into segments. The first and last segment of every row contains Row Indicator data. The Row Indicator data always includes the current row number, and also includes one of the total number of rows in the symbol, the total number of columns in the symbol, or the security level of the symbol. Thus, the first segment of every third row encodes the total number of rows in the symbol, so the decoder can quickly determine how many rows it must detect. This information is also stored in the last segment of the row. PDF417 symbols employ varying levels of Reed-Solomon error correction coding to allow error detection and correction if part of the symbol is damaged or missing.
MaxiCode is a matrix-type code developed by UPS for parcel tracking. MaxiCode symbols have a distinctive xe2x80x98bulls-eyexe2x80x99 finder pattern located at the centre of the symbol. The code elements are hexagonal in shape and are placed on a hexagonal grid 30 elements wide by 33 elements high. The code supports only one size, and one information density, and is approximately 1.12 inches by 1.05 inches. MaxiCode symbols also employ Reed-Solomon error correction encoding to allow errors to be detected and corrected. In a MaxiCode symbol, data can be organized into a primary message and a secondary message. The primary message consists of 50% error control bits to ensure that this data is correctly read even if the secondary message is damaged.
Due to the way that 2D bar codes are generated, there are a number of common problems experienced in attempting to image and decode bar code symbols. Typically, damage to the code occurs along the perimeter of the code. This may be due to destruction of the label on which the code is printed (during shipping or handling, for example), marks made on the code when writing on the label, or other physical damage.
The method by which the code is imaged may also introduce defects to the image that affect the readability of the 2D bar code. Variations in illumination or incorrect exposure, for example, may result in low contrast between black and white marks. This typically occurs at the edges of the code, especially when the code is not printed on a flat surface. Data Matrix codes are especially susceptible to perimeter damage. If portions of the xe2x80x98Lxe2x80x99 pattern are missing, decoders may not be able to locate and identify the code. Additionally, missing sections of the alternating black and white marks along the other two sides of the code may prevent the reader from determining the proper array size. MaxiCode symbols generated using a spiral message sequence often have large amounts of damage to the secondary message. Perimeter damage to PDF417 codes will affect the top and bottom rows of data as well as the start and stop patterns. Although these codes include error-correcting schemes, the extra codewords required to be able to correct errors in the data occupy a large amount of the code area. This limits the amount of data that can be stored in a code of a certain size.
Reed-Solomon error correction, now used by almost all 2D bar codes, is a byte-correcting scheme that is widely used for digital storage applications in fields such as telecommunications, for example. Reed-Solomon error correcting codewords are incorporated along with xe2x80x9cdataxe2x80x9d codewords to form an integrated message. Conceptually, one Reed-Solomon error correcting codeword can be used to correct one damaged data codeword if the damage is known in advance. Damaged codewords which are identified in advance are known as xe2x80x9cerasures.xe2x80x9d Two Reed-Solomon codewords are required to correct xe2x80x9cunknownxe2x80x9d data damagexe2x80x94which is known as an xe2x80x9cerror.xe2x80x9d A full discussion of the structure, generation and decoding of Reed-Solomon codes can be found in the references. Briefly, a Reed-Solomon message consists of a number of codewords, consisting of s bits each. The message is n codewords long, with k data codewords and nxe2x88x92k parity codewords. The message is described by the form RS(n,k).
Damage to a Reed-Solomon message is either in the form of errors or erasures. An error occurs when a codeword in an unknown location is damaged or wrong. An erasure occurs when the position of the damaged codeword is known. The measure of the number of errors and erasures that a message can correct is given by 2t=nxe2x88x92k. Reed-Solomon error correcting codewords can correct up to t errors or 2t erasures. Based on this fact, the ability to detect and identify the location of errors in advance can potentially double the effectiveness of the Reed-Solomon encoding, allowing up to 2 times the number of damaged codewords to be corrected.
There have been attempts made in the past to take advantage of this property of Reed-Solomon error-correction. In U.S. Pat. No. 5,533,084, Ackley describes an improved error correction algorithm for use with Code One symbols. Code One is a matrix-type 2D bar code. The invention takes advantage of the specific properties of the Code One symbol to improve the error correction and detection capability of the reader over a standard reader. The algorithm described by Ackley first attempts to decode the symbol assuming there are no errors. If this attempt fails, the reader attempts to decode the symbol again, but this time inserting Code One pad characters over obscured portions of the code. The position and quantity of required pad characters is determined by identifying the position and quantity of existing pad characters and comparing to known symbol size. Ackley""s invention adds a significant amount of processing complexity to the scanning portion of the reader but uses standard decoding software to complete the decoding of the corrected, scanned image. The increased scanning complexity results in a greatly increased decoding time.
Thus, there is a need for an optical code reading system that maximizes the error-correcting potential of optical code symbols without sacrificing decoding speed.
An improved barcode reading system and method is disclosed. There are typically only two reasons why a bar code is not successfully read: 1) it cannot be located within the field of view due to start bar/finder pattern damage or, 2) the physical damage to the symbol exceeds the error correction capability. The instant invention addresses both of these issues. It enhances the ability of a reader to locate a symbol within a field of view and it enhances the error-correcting properties of the encoding scheme commonly used in 2D bar codes. In one embodiment, a global feature determination algorithm is used to offset the effects of damaged finder patterns and missing symbol perimeters. A local feature extraction algorithm is then used to detect high-level symbol information such as the code type, symbol size, and the number of rows and columns in the symbol. The local feature extraction algorithm also identifies those missing portions of a damaged symbol and marks each missing data bit location with a predetermined indicator. A decoding algorithm then interprets the missing bit indicator as an error of known location (e.g., an xe2x80x9cerasurexe2x80x9d), thereby nearly doubling the error correcting strength of all bar codes employing the Reed-Solomon error correction scheme.